#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
using std::cerr;

namespace test
{
struct t_some_struct
{
	unsigned a;
	t_some_struct(unsigned a_):a(a_){}
	t_some_struct(){}
	static unsigned cnt_swaps;
	static unsigned cnt_ctors;
	t_some_struct(const t_some_struct& o): a(o.a){++cnt_ctors;}
};
unsigned t_some_struct::cnt_swaps = 0;
unsigned t_some_struct::cnt_ctors = 0;

void swap(t_some_struct& a, t_some_struct& b)
{
	std::swap(a.a,  b.a);
	++a.cnt_swaps;
}
bool operator <(const t_some_struct& a, const t_some_struct& b)
{
	return a.a < b.a;
}
std::ostream& operator << (std::ostream& os, const t_some_struct& b)
{
	os << b.a;
	return os;
}
}

using test::t_some_struct;

#include <stlhelper.h>
/*
void order_by_sorted_indices_new(std::vector<t_some_struct>& data, std::vector<unsigned>& indices)
{
	//using std::swap;
	assert(data.size() >= indices.size());

	std::vector<unsigned> curr_order(indices.size());
	for (unsigned i = 0; i < indices.size(); ++i)
		curr_order[indices[i]] = i;

	for (unsigned j = 0; j < indices.size(); ++j)
	{
		assert(indices[j] < data.size());
		if (curr_order[j] == j)
			continue;
		unsigned index  = indices[j];
		swap(indices[curr_order[j]], indices[j]);
		swap(curr_order[j], curr_order[index]);
		swap(data[j], data[index]);

	}
}
void order_by_sorted_indices_new(std::vector<t_some_struct>& data, std::vector<unsigned>& indices)
{
	using std::swap;
	assert(data.size() >= indices.size());

	cerr << "data   : ";
	for (unsigned i = 0; i < data.size(); ++i)
		cerr << data[i].a << ",";
	cerr << "\n";
	cerr << "indices: ";
	for (unsigned i = 0; i < indices.size(); ++i)
		cerr << indices[i] << ",";
	cerr << "\n";

	cerr << "indexed: ";
	for (unsigned i = 0; i < indices.size(); ++i)
		cerr << data[indices[i]].a << ",";
	cerr << "\n\n";

	std::vector<unsigned> curr_order(indices.size());
	for (unsigned i = 0; i < indices.size(); ++i)
		curr_order[indices[i]] = i;

	// copy old values to new container in sorted order
	for (unsigned j = 0; j < indices.size(); ++j)
	{
		cerr << "indices[" << j << "] " << indices[j] << ", indices[indices[" << j << "]] = " << indices[indices[j]] << "\n";
		assert(indices[j] < data.size());
		if (curr_order[j] == j)
			continue;
		unsigned index  = indices[j];
		swap(indices[curr_order[j]], indices[j]);
		swap(curr_order[j], curr_order[index]);
		swap(data[j], data[index]);
		cerr << "data   : ";
		for (unsigned i = 0; i < data.size(); ++i)
			cerr << data[i].a << ",";
		cerr << "\n";
		cerr << "indices: ";
		for (unsigned i = 0; i < indices.size(); ++i)
			cerr << indices[i] << ",";
		cerr << "\n";

		cerr << "indexed: ";
		for (unsigned i = 0; i < indices.size(); ++i)
			cerr << data[indices[i]].a << ",";
		cerr << "\n\n";

	}
}

1 4 3 2 0	data			swap 0 4		swap data[0] with data[indices[0]]
4 0 3 2 1	indices			swap 0 1		swap indices[0] with indices[data[0]]


0 4 3 2 1	data   			swap 1 4        swap data[1] with data[indices[1]]
0 4 3 2 1	indices			swap 1 4        swap indices[1] with indices[data[1]]

0 1 3 2 4	data			swap 2 3
0 1 3 2 4	indices			swap 2 3

0 1 2 3 4	data
0 1 2 3 4	indices

*/
/*
#include <list>
int main (int argc, char *argv[])
{
	unsigned VEC_SIZE = 100;
	std::deque<t_some_struct> list;
	std::vector<std::deque<t_some_struct>::iterator> swap_vec;
	for (unsigned i = 0; i < VEC_SIZE; ++i)
	{
		list.push_front(t_some_struct(i));
		swap_vec.push_back(list.begin());
	}
	cerr << "swap randomly\n";
	for (unsigned i = 0; i < swap_vec.size(); ++i)
	{
		unsigned a = rand() % VEC_SIZE;
		unsigned b = rand() % VEC_SIZE;
		if (a != b)
			swap(*swap_vec[a], *swap_vec[b]);
	}
	cerr << "\nswap = " << t_some_struct::cnt_swaps << "\n";
	cerr << "\nctors = " << t_some_struct::cnt_ctors << "\n";


	std::copy(list.begin(),  list.end(),  std::ostream_iterator<t_some_struct> (std::cout, ","));
	std::cout << "\n";
	sort(list.begin(), list.end());
	std::copy(list.begin(),  list.end(),  std::ostream_iterator<t_some_struct> (std::cout, ","));
	cerr << "swap = " << t_some_struct::cnt_swaps << "\n";
	cerr << "\nctors = " << t_some_struct::cnt_ctors << "\n";


}
*/
int main (int argc, char *argv[])
{
	unsigned VEC_SIZE = 100;
	std::vector<t_some_struct> vec;
	for (unsigned i = 0; i < VEC_SIZE; ++i)
		vec.push_back(t_some_struct(i));
	cerr << "swap randomly\n";
	for (unsigned i = 0; i < vec.size(); ++i)
	{
		unsigned a = rand() % VEC_SIZE;
		unsigned b = rand() % VEC_SIZE;
		if (a != b)
			swap(vec[a], vec[b]);
	}
	cerr << "\nswap = " << t_some_struct::cnt_swaps << "\n";


	for (unsigned i = 0; i < vec.size(); ++i)
		cerr << vec[i].a << ",";
	cerr << "\n";

	sort_with_swaps(vec);
/*
	std::vector<unsigned> indices(vec.size());
	for (unsigned i = 0; i < vec.size(); ++i)
		indices[vec[i].a] = i;
	cerr << "indices\n";
	for (unsigned i = 0; i < indices.size(); ++i)
		cerr << indices[i] << ",";
	cerr << "\n\n";

	t_some_struct::cnt_swaps = 0;
	order_by_sorted_indices(vec, indices);

*/


	for (unsigned i = 0; i < vec.size(); ++i)
		cerr << vec[i].a << ",";
	cerr << "\n";

	cerr << "swap = " << t_some_struct::cnt_swaps << "\n";





	//
	//	same but with unsigned instead of struct
	//
	cerr << "\n\nunsigned\n\n";

	std::vector<unsigned> vec_u;
	for (unsigned i = 0; i < VEC_SIZE; ++i)
		vec_u.push_back(unsigned(i));
	cerr << "swap randomly\n";
	for (unsigned i = 0; i < vec_u.size(); ++i)
	{
		unsigned a = rand() % VEC_SIZE;
		unsigned b = rand() % VEC_SIZE;
		if (a != b)
			std::swap(vec_u[a], vec_u[b]);
	}


	for (unsigned i = 0; i < vec_u.size(); ++i)
		cerr << vec_u[i] << ",";
	cerr << "\n";

  std::vector<unsigned> indices_u(vec_u.size());
  for (unsigned i = 0; i < vec_u.size(); ++i)
	indices_u[vec_u[i]] = i;
	cerr << "indices_u\n";
	for (unsigned i = 0; i < indices_u.size(); ++i)
		cerr << indices_u[i] << ",";
	cerr << "\n\n";

	order_by_sorted_indices(vec_u, indices_u);
	for (unsigned i = 0; i < vec_u.size(); ++i)
		cerr << vec_u[i] << ",";
	cerr << "\n";


	return(0);
}
